/***********************************************************************************
*
*                      基于互斥锁和线性表探测再散列的线程间缓存实现
*                                  
*                                  author：xuhr
*
************************************************************************************/
#include <iostream> 
#include <string>	    //引用std string操作
#include <assert.h>     //引用断言操作
#include <pthread.h>    //引用线程操作
#include <mutex>        //引用互斥锁操作

namespace cache
{
    enum
    {
        HEAD_SIZE = 32  //线性表大小
    };

    //缓存数据类 CCacheData
    class CCacheData
    {
    public:
        CCacheData():m_data_1(0), m_data_2(0), m_data_3("")
        {
        }
        int m_data_1;
        double m_data_2;
        std::string m_data_3;
    };

    //缓存节点类 SNode
    class SNode
    {
    public:
        CCacheData *m_pData;                                    //缓存数据
        SNode *m_pNext;                                         //指向下一个缓存节点（初始化为null）
        pthread_t m_nTid;                                       //线程号，唯一标识一个缓存节点空间
        int story_times;                                        //标记该节点空间被缓存次数，初始为0

    public:
        SNode()
        {
            m_pData = new CCacheData;                           //节点初始化，可以看到是用new开辟的堆空间，这样这个空间是不会随着对象析构而被释放，从而达到缓存的目的
            m_pNext = NULL;                                     
            m_nTid = 0;                                         //线程号初始化为0
        }
        ~SNode()    // !!!!去掉析构函数内容则可以变成跨进程的缓存，但堆区的缓存空间需要想其它办法释放
        {                  
            if( NULL != m_pData )
                delete m_pData;
        }
    };

    //缓存类 CThreadVariable
    class CThreadVariable :public SNode
    {
    private:
        SNode *m_pNode;             //缓存区空间首地址（哈希表首地址)
        pthread_mutex_t m_mutex;    //临界区类型，用于初始化互斥锁
    public:
        CThreadVariable()
        {
            m_pNode = new SNode[HEAD_SIZE];     //在堆区开辟一个动态数组，大小为32，堆区开辟的空间在逻辑上是连续的，可以用数组方式进行随机存取，这个动态数组就是哈希的线性表
            assert(m_pNode != NULL);            //断言开辟空间成功，避免在堆区开32个空间的缓存区失败的情况，如果开辟失败直接就终止退出
            pthread_mutex_init(&m_mutex, 0);    //初始化一个线程互斥锁，其中m_mutex是一个互斥量结构，用于初始化一个互斥锁，0表示构建默认的互斥锁，可以由本线程来解锁
            story_times = 0;
        }
        ~CThreadVariable()
        {
            pthread_mutex_destroy( &m_mutex);
            SNode*    pNode = NULL;
            SNode*    pNext = NULL;
            for(int i = 0; i < HEAD_SIZE; ++i)
            {
                pNode = m_pNode[i].m_pNext;
                while( pNode)
                {
                    pNext = pNode->m_pNext;
                    delete pNode;
                    pNode = pNext;
                }
            }
            delete[] m_pNode;
        }
    public:
        //缓存类与外围唯一交互方法：根据相对线程id号探测缓存空间一个可以存储的的节点空间，返回这个节点空间地址（哈希表使用简单的线性探测再散列）
        SNode *get_var()
        {
            pthread_t nTid = pthread_self();                 //获取进程内线程的相对线程id

            int index = ((int)nTid) % HEAD_SIZE;             //tid号 映射-> index，这个index就是当前线程在线性表中要探测的初始位置
            index = index < 0 ? -index : index;              //index必须非负，因为数组下标从0开始

            SNode *pHead = &m_pNode[index];                  //基于取模映射探测index对应数组下标空间，接下来的探测会有三种场景
            /*
                场景1：哈希探测线性表时不用散列  判断 tid号 映射-> index 取的array[index]空间是不是已经有线程在缓存了
                当m_nTid = 0 时，说明这个array[index]空间还没有线程来缓存资料，本线程占据这个空间，并将空间地址赋值给 pHead，后面通过insert函数往空间放数据
                这种情况在只有少数线程要进行缓存或者刚开始进行缓存的时候会更容易遇到，所以放在三个场景第一个位置，最容易被触发
            */
            if (pHead->m_nTid == 0)                         
            {
                pthread_mutex_lock(&m_mutex);               //上锁，此时别的线程不可以来访问整个缓存空间，假设还有其线程准备进行缓存，需要等待当前线程解锁才能进行缓存
                if (pHead->m_nTid == 0)                     //上锁期间防止有其它线程占掉这个空间，再次判断
                {
                    pHead->m_nTid = nTid;                   //表示这个缓存数组位置的空间归这个线程号
                }
                pthread_mutex_unlock(&m_mutex);             //解锁
            }
            /*
                场景2：哈希探测线性表刚好探测到了自己，判断 tid号 映射-> index 取的array[index]空间恰好就是本线程占据的空间，那么直接返这个空间的地址
                这种情况是线程内进行过一次缓存了，但在线程被kill之前还要读取一次刚刚缓存的内容
            */
            if (pHead->m_nTid == nTid)
            {
                return pHead;
            }
            /*
                场景3：哈希探测线性表发生碰撞 判断 tid号 映射-> index 取的array[index]空间被其它线程占掉了
                进入散列array[index].list，遍历散列，如果有发现本线程占据的空间，则返回这个空间，否则在最末端位置插入一个新的节点给本线程，后面通过insert函数往空间放数据
                如果参与缓存的线程数量多的话（大于32）这个反而又是最常见的情况
            */      
            pthread_mutex_lock(&m_mutex);                   //上锁，本线程进行占据操作期间，其它线程不可以来操作缓存区               
            SNode *pNode = pHead->m_pNext;                  //获取当前位置array[index]下的list空间，注意不是array[index+1]，而是array[index]->m_pNext，这是一个链表结构
            pthread_mutex_unlock(&m_mutex); 
            while (pNode)   //这个while是遍历散列的过程
            {
                if (pNode->m_nTid == nTid)
                {
                    return pNode;
                }
                pNode = pNode->m_pNext;
            }
            return insert(pHead);
        }

        //缓存类与外围交互方法，通过传入线程id去探测节点空间（这个方法本不应存在，线程id应由缓存类自己获取来保证缓存安全，是为了验证缓存空间数据是否正确而写，实际使用时应当删除该方法）
        SNode *get_var(pthread_t nTid)
        {
            int index = ((int)nTid) % HEAD_SIZE;             //tid号 映射-> index，这个index就是当前线程在线性表中要探测的初始位置
            index = index < 0 ? -index : index;              //index必须非负，因为数组下标从0开始

            SNode *pHead = &m_pNode[index];                  //基于取模映射探测index对应数组下标空间，接下来的探测会有三种场景

            /*
                场景1：哈希探测线性表时不用散列  判断 tid号 映射-> index 取的array[index]空间是不是已经有线程在缓存了
                当m_nTid = 0 时，说明这个array[index]空间还没有线程来缓存资料，本线程占据这个空间，并将空间地址赋值给 pHead，后面通过insert函数往空间放数据
                这种情况在只有少数线程要进行缓存或者刚开始进行缓存的时候会更容易遇到，所以放在三个场景第一个位置，最容易被触发
            */
            if (pHead->m_nTid == 0)                         
            {
                pthread_mutex_lock(&m_mutex);               //上锁，此时别的线程不可以来访问整个缓存空间，假设还有其线程准备进行缓存，需要等待当前线程解锁才能进行缓存
                if (pHead->m_nTid == 0)                     //上锁期间防止有其它线程占掉这个空间，再次判断
                {
                    pHead->m_nTid = nTid;                   //表示这个缓存数组位置的空间归这个线程号
                }
                pthread_mutex_unlock(&m_mutex);             //解锁
            }

            /*
                场景2：哈希探测线性表刚好探测到了自己，判断 tid号 映射-> index 取的array[index]空间恰好就是本线程占据的空间，那么直接返这个空间的地址
                这种情况是线程内进行过一次缓存了，但在线程被kill之前还要读取一次刚刚缓存的内容
            */
            if (pHead->m_nTid == nTid)
            {
                return pHead;
            }

            /*
                场景3：哈希探测线性表发生碰撞 判断 tid号 映射-> index 取的array[index]空间被其它线程占掉了
                进入散列array[index].list，遍历散列，如果有发现本线程占据的空间，则返回这个空间，否则在最末端位置插入一个新的节点给本线程，后面通过insert函数往空间放数据
                如果参与缓存的线程数量多的话（大于32）这个反而又是最常见的情况
            */      
            pthread_mutex_lock(&m_mutex);                   //上锁，本线程进行占据操作期间，其它线程不可以来操作缓存区               
            SNode *pNode = pHead->m_pNext;                  //获取当前位置array[index]下的list空间，注意不是array[index+1]，而是array[index]->m_pNext，这是一个链表结构
            pthread_mutex_unlock(&m_mutex);                 
            while (pNode)   //这个while是遍历散列的过程
            {
                if (pNode->m_nTid == nTid)
                {
                    return pNode;
                }
                pNode = pNode->m_pNext;
            }

            return insert(pHead);
        }

        //获取缓存区首地址（该方法不应存在，仅为了测试而存在，实际使用时应当删除该方法）
        SNode *get_SNodeAddress()
        {
            return m_pNode;
        }

    private:

        //散列时开新缓存空间方法
        SNode *insert(SNode *pHead)
        {
            SNode *pNode = new SNode;           //散列时要开辟新的存储空间
            pNode->m_nTid = pthread_self();

            //新开的空间插入到散列中，插到散列最前面位置
            pNode->m_pNext = pHead->m_pNext;
            pthread_mutex_lock(&m_mutex);       //线程并发操作缓存空间可能会导致散列的空间永久丢失，故要上锁
            pHead->m_pNext = pNode;             
            pthread_mutex_unlock(&m_mutex);

            return pNode;                       //返回散列开辟的新空间地址
        }
    };
}

namespace bussiness
{
    //业务类
    class CBussinessCache
    {
    public:
        // 缓存数据
        // const cache::CCacheData     IN
        // 缓存数据失败返回0，否则返回1
        static int story_dataIntoCache(const cache::CCacheData bussinessData_)
        {
            *(m_cThreadVariable.get_var()->m_pData) = bussinessData_;
            ++m_cThreadVariable.get_var()->story_times;

            if(bussinessData_.m_data_1 == (m_cThreadVariable.get_var()->m_pData)->m_data_1 &&
               bussinessData_.m_data_2 == (m_cThreadVariable.get_var()->m_pData)->m_data_2 &&
               bussinessData_.m_data_3 == (m_cThreadVariable.get_var()->m_pData)->m_data_3) 
               return 1;
            else return 0;     
        }

        // 获取缓存的数据 
        // cache::CCacheData   IN
        // 获取缓存数据为空则返回0，否则返回1
        static int get_dataFromCache(cache::CCacheData &bussinessData_)
        {
            bussinessData_ = *(m_cThreadVariable.get_var()->m_pData);
            if(m_cThreadVariable.get_var()->story_times  >0) return 1;
            else return 0;
        }
    public:
        static cache::CThreadVariable m_cThreadVariable;  //将缓存类声明为静态成员变量，这样这个缓存变量属于整个类的
    };
}


/*******************************************************************************************************************************************************************
*
*                              由此开始进行调试，调试前请务必读懂下面这段文字
*
*    首先得了解几个重要的概念：
*           c++的栈区、堆区、全局区
*           c++的全局变量和static关键字
*           这里不做介绍，必须要先理解这几个概念才能看懂下面的内容
*
*    先看一个场景：
*           假设上面写的缓存类为类A，缓存类A被main函数调用生成缓存对象a1，如果放在大工程里，这个不一定是main，可能是其它模块
*           正常情况下，如果不将缓存类A声明为静态变量或全局变量，对象a1会被默认声明为局部变量，而对象的实体被存放在了栈区
*           同时对象a1被构造的时候会在堆区开辟出一个哈希存储表t1，a1里面的成员变量存有哈希表t1的首地址
*           可以通过在栈区的a1去访问堆区的哈希表，而a1对象析构时，会把栈区的对象a1销毁，同时会试图去销毁堆区的哈希表t1，如果缓存类A的析构函数有delete 操作的话
*           
*           这时假设main又调用了一次缓存类A构造了一个缓存对象a2
*           于是又生成了一个放在栈区的a2和一个放在堆区的t2，依次类推还有a3 t3 a4 t4...
*           于是会发现，这个堆区的缓存区随着缓存对象的不断构造和析构也在不断的new和delete，main中不同的缓存对象访问的居然不是同一个缓存区？那不乱套了嘛
*           我们想要的缓存效果是，在main函数销毁前，不管缓存对象构造多少次，在堆区始终只存在一个缓存区t1，就是第一次创建对象a1时生成的那个，不管谁访问，始终都是访问这个缓存区t1
*           
*           要实现这样的效果，必须借助全局区，不能让缓存对象放在栈区，这样在main函数这个进程销毁前，谁声明缓存对象都是访问的全局区那唯一的一个缓存区对象a1
*           自然，通过这个缓存区对象a1访问的哈希表也是唯一的那个t1
*           
*     实现方法如下：
*           一、将这个缓存类声明为static类型（不够灵活）
*           二、将缓存对象声明为全局变量（放在main函数前面构造对象，显然这个方法太差了，放在main函数前声明那创建这缓存类个意义何在？不如直接定义一个全局变量去存储）
*           三、缓存类作为业务类的静态成员变量，这样这个缓存就是用于描述整个类的，而非某一个对象（这个方法好，工程里一般都用方法三，灵活配置）
*
*           接下来的调试介绍方法一、三的实现
*
*     调试过程有几个注意点：
*           1、cout不是原子操作，线程不安全，printf是原子操作，故多线程并发时，用cout即使上锁也会导致输出的信息混乱，尽量用printf，如果一定要用cout的话，请先实现它的线程安全
*           2、pthread_create 创建线程所需的时间远大于 for循环运行时间，不能将数据初始化和线程创建放在一个for循环里
*           3、c++的静态成员要在类内声明，在类外完成初始化
* 
********************************************************************************************************************************************************************/
std::mutex valMutex;    //线程锁

//线程函数  供方法一测试  入参：待缓存的数据的空间地址
void* thread1(void* data)
{   
    //从传进来的数据地址中读取要缓存的cashData类型数据
    const cache::CCacheData data_ = *((cache::CCacheData*)data);

    //创建静态缓存（这样无论线程函数被执行多少次，缓存变量都只会被创建一次在堆区，当调用它的函数test_cache1销毁时，缓存变量和缓存区才会被销毁）
    static cache::CThreadVariable cThreadVariable;

    //打印线程id，打印过程需要上互斥锁，否则多线程同时抢占打印资源，会造成打印内容混乱
    valMutex.lock();
    pthread_t tid = pthread_self();
    printf("test_cache1()创建线程 %d 成功\n", (int)tid);
    valMutex.unlock();

    //哈希表空间探测并存储
    *(cThreadVariable.get_var()->m_pData) = data_;

    //打印存储效果
    valMutex.lock();
    int data1 = (cThreadVariable.get_var()->m_pData)->m_data_1;
    double data2 = (cThreadVariable.get_var()->m_pData)->m_data_2;
    std::string data3 = (cThreadVariable.get_var()->m_pData)->m_data_3;
    printf("存储数据: %d | %lf | %s 到缓存区成功",data1, data2, data3.c_str());
    printf("\n");
    printf("本次线程函数创建的堆区缓存，缓存区首地址是: %d", (int*)(cThreadVariable.get_SNodeAddress()));
    printf("\n");
    valMutex.unlock();
}

int test_cache1()
{   
    #define NUM_THREADS 10          //并发线程数量，修改此值来增加并发数量

    //1、创建线程id, 存储到tids数组中，后续要通过这个tids数组访问缓存的内容，线程id从0开始
    pthread_t tids[NUM_THREADS];

    //2、创建线程需要存储的数据
    cache::CCacheData data_list[NUM_THREADS];
    for(int i=0; i<NUM_THREADS; ++i)
    {
        data_list[i].m_data_1 = i;
        data_list[i].m_data_2 = i; 
        data_list[i].m_data_3 = "I am string";
    }
    
    //3、模拟多个线程并发缓存数据
    for(int i=0; i<NUM_THREADS; ++i)
    {
        int res = pthread_create(&tids[i], NULL, thread1, (void*)&data_list[i]);
        if (res){
            std::cout<<"test_cache1()创建线程 "<<tids[i]<<" 失败"<<std::endl;
            exit(-1);
        }
    }

    //4、等待所有线程结束
    for(int i=0; i<NUM_THREADS; ++i)
    {
        int res = pthread_join(tids[i], NULL);
        if (res){
            std::cout<<"test_cache1()结束线程 "<<tids[i]<<" 失败"<<std::endl;
            exit(-1);
        }
    }

    //5、通过tids查看刚刚通过并发线程缓存的数据，验证线程并发情况下缓存的效果是否正确（这里不做实现了，因为静态缓存是定义成了一个局部变量，不太好处理）
    //std::cout<<"test_cache1()创建的线程并发缓存成功, 通过线程id访问, 结果如下:"<<std::endl;
    /*
    for(int i=0; i<NUM_THREADS; ++i)
    {
        const cache::CCacheData = *(cThreadVariable.get_var()->m_pData);
        std::cout<<"线程 "<<tids[i]<< "缓存的数据是 "<<
    }*/
}

cache::CThreadVariable bussiness::CBussinessCache::m_cThreadVariable;   //静态变量要在类外初始化，这里不是定义一个全局变量，是完成静态成员的初始化
int test_cache2()
{
    //线程并发缓存的情景在方法一中已验证，这里不再模拟多线程操作，仅用一个主线程进行多次缓存
    //下面这段代码模拟10个业务对象依次进行缓存，每个对象都会覆盖前面
    for(int i = 0; i<10; ++i)
    {
        bussiness::CBussinessCache myBussiness; //每次循环都声明一个新的业务对象，业务对象调用内部方法进行数据缓存
        cache::CCacheData myData;
        myData.m_data_1 = i;
        myData.m_data_2 = i;
        myData.m_data_3 = "I am string";

        //获取上次缓存数据，多次调用缓存对象缓存数据时，缓存中存储的应当是上一次缓存的数据
        cache::CCacheData myDataTmp;
        if(1 == myBussiness.get_dataFromCache(myDataTmp))
            std::cout<<"当前缓存中的数据是："<<myDataTmp.m_data_1<<" | "<<myDataTmp.m_data_2<<" | "<<myDataTmp.m_data_3<<std::endl;
        else std::cout<<"当前缓存中的数据为空"<<std::endl;

        //缓存本次数据
        if(1 == myBussiness.story_dataIntoCache(myData))
            std::cout<<"更新数据到缓存中："<<myData.m_data_1<<" | "<<myData.m_data_2<<" | "<<myData.m_data_3<<std::endl;
        else std::cout<<"缓存本次数据失败"<<std::endl;
        std::cout<<"--------------------------------"<<std::endl;
    }
}

int main()
{
	test_cache1();  //测试上文介绍的方法一
    //test_cache2();  //测试上文介绍的方法三
}



